// 2维矩阵的广度搜索
// 通过广度搜索的方式，从矩阵中的任意一个点开始，遍历矩阵中所有的点

const zddTool = require('../commonTool/zddtool.js');

class MatrixBFS {
    /**
     * 2维矩阵的广度搜索
     * @param {Array[][]} matrix 二维数组
     */
    constructor(matrix) {
        this.matrix = matrix;
        this.info = {
            rows: this.matrix.length,
            cols: this.matrix[0].length,
            startPoint: [0, 0],
        };

        console.log(`MatrixBFS init finish`);
        this.print();
    }

    /**
     * 顺时针 上右下左
     */
    static directions = [
        [-1, 0], // 上
        [0, 1], // 右
        [1, 0], // 下
        [0, -1], // 左
    ];

    /**
     * 设置BFS起点坐标，行列都从0开始
     * @param {Number} row
     * @param {Number} column
     */
    setStartPoint(row, column) {
        // TODO: 边界校验
        this.info.startPoint = [row, column];
    }

    /**
     * 以BFS的方式轮询整个矩阵，返回矩阵中的每一个节点
     * @returns
     */
    bfs() {
        console.log(`MatrixBFS bfs`);
        let ret = [];
        let { info } = this; // 提取矩阵中的矩阵行数，列数等信息
        let allVisited = new Array(info.rows * info.cols).fill(false); // 所有节点是否被访问 -> 用来判断广度搜索是否已经完成
        let previousNodes = []; // 第n轮广度搜索时，上一轮的所有节点
        let loopCount = 0; // 为了避免代码错误，设置超过100次强制跳出循环

        // 从矩阵的起点开始，往外扩散，直到轮询外矩阵的所有元素
        while (!allVisited.every((ele) => ele === true) || loopCount === 100) {
            let newPreviousNodes = [];
            loopCount++;

            // 首次循环加入起点后就返回
            if (previousNodes.length === 0) {
                const x = info.startPoint[0];
                const y = info.startPoint[1];
                ret.push(this.matrix[x][y]);

                previousNodes.push([x, y]);
                allVisited[x * info.cols + y] = true;

                this.print(allVisited);
                continue;
            }

            previousNodes.forEach((ele) => {
                const preX = ele[0];
                const preY = ele[1];

                // 顺时针搜索周边节点
                MatrixBFS.directions.forEach((direction) => {
                    const x = direction[0] + preX;
                    const y = direction[1] + preY;

                    // 边界判断
                    if (x >= 0 && x < info.rows && y >= 0 && y < info.cols) {
                        // 如果节点已经访问过了，也不需要再次访问
                        if (allVisited[x * info.cols + y] === false) {
                            ret.push(this.matrix[x][y]);
                            newPreviousNodes.push([x, y]);
                            allVisited[x * info.cols + y] = true;
                            console.log(
                                `push x:${x} y:${y} value:${this.matrix[x][y]}`
                            );
                        }
                    }
                });
            });

            previousNodes = newPreviousNodes;

            this.print(allVisited);

            if (loopCount === 100) {
                console.log(`[MatrixBFS]: BFS Failure 100 loops`);
                break;
            }
        }

        return ret;
    }

    /**
     * 通过console.log绘制矩阵
     */
    print(visitArray) {
        /**
         * -------------
         * | 1 | 2 | 3 |
         * | 4 |[5]| 6 |
         * | 7 | 8 | 9 |
         * -------------
         */
        // 获取所有元素的字符串最大长度

        let maxNumLen = 3; // 默认值是3
        const { info } = this;

        this.matrix.forEach((row) => {
            row.forEach((ele) => {
                if (ele.length > maxNumLen) {
                    maxNumLen = ele.length;
                }
            });
        });

        const eleWidth = maxNumLen + 4;

        const strBorder = new Array(eleWidth * info.cols)
            .fill('-')
            .join()
            .replace(/,/g, '');

        console.log(strBorder);
        this.matrix.forEach((row, _rIdx) => {
            let strRow = '|';
            row.forEach((ele, _cIdx) => {
                let strEle = `${ele}`;
                if (
                    visitArray != null &&
                    visitArray[_rIdx * info.cols + _cIdx] === true
                ) {
                    strEle = `[${strEle}]`;
                }

                while (strEle.length < eleWidth - 2) {
                    strEle = ` ${strEle} `;
                }
                strEle = strEle.slice(0, eleWidth);
                strRow += `${strEle}|`;
            });
            console.log(strRow);
        });
        console.log(strBorder);
    }
}

// test
let matrix = zddTool.new2DMatrix(5, 4, -1);
// let matrix = [
//     [1, 2, 3],
//     [4, 5, 6],
//     [7, 8, 9],
// ];

let matrixBFS = new MatrixBFS(matrix);
// matrixBFS.setStartPoint(1, 1);
console.log(`[MatrixBFS]: BFS loop start`);
const bfsArray = matrixBFS.bfs();
console.log(`[MatrixBFS]: final bfs array is ${JSON.stringify(bfsArray)}`);
